{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #蓄水"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: storeWater"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #蓄水"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "给定 N 个无限容量且初始均空的水缸，每个水缸配有一个水桶用来打水，第 `i` 个水缸配备的水桶容量记作 `bucket[i]`。小扣有以下两种操作：\n",
    "-  升级水桶：选择任意一个水桶，使其容量增加为 `bucket[i]+1`\n",
    "-  蓄水：将全部水桶接满水，倒入各自对应的水缸\n",
    "\n",
    "每个水缸对应最低蓄水量记作 `vat[i]`，返回小扣至少需要多少次操作可以完成所有水缸蓄水要求。\n",
    "\n",
    "注意：实际蓄水量 **达到或超过** 最低蓄水量，即完成蓄水要求。\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`bucket = [1,3], vat = [6,8]`\n",
    ">\n",
    ">输出：`4`\n",
    ">\n",
    ">解释：\n",
    ">第 1 次操作升级 bucket[0]；\n",
    ">第 2 ~ 4 次操作均选择蓄水，即可完成蓄水要求。\n",
    "![vat1.gif](https://pic.leetcode-cn.com/1616122992-RkDxoL-vat1.gif)\n",
    "\n",
    "\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`bucket = [9,0,1], vat = [0,2,2]`\n",
    ">\n",
    ">输出：`3`\n",
    ">\n",
    ">解释：\n",
    ">第 1 次操作均选择升级 bucket[1]\n",
    ">第 2~3 次操作选择蓄水，即可完成蓄水要求。\n",
    "\n",
    "**提示：**\n",
    "- `1 <= bucket.length == vat.length <= 100`\n",
    "- `0 <= bucket[i], vat[i] <= 10^4`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [o8SXZn](https://leetcode.cn/problems/o8SXZn/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [o8SXZn](https://leetcode.cn/problems/o8SXZn/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3]\\n[6,8]', '[9,0,1]\\n[0,2,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        mx = max(vat)\n",
    "        if mx == 0:\n",
    "            return 0\n",
    "        ans = inf\n",
    "        for x in range(1, mx + 1):\n",
    "            y = sum(max(0, (v + x - 1) // x - b) for v, b in zip(vat, bucket))#x是蓄水次数，y是升级次数\n",
    "            ans = min(ans, x + y)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        l = len(bucket)\n",
    "        if vat == [0] * l:return 0\n",
    "        res = 1000000\n",
    "        x = 1\n",
    "        for x in range(1,10102):\n",
    "            m = x\n",
    "            for i in range(l):\n",
    "                vat[i] -= bucket[i]\n",
    "                if vat[i] > 0:\n",
    "                    m += vat[i]//x + (0 if vat[i]%x==0 else 1)\n",
    "            if m < res:res = m\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        l = len(bucket)\n",
    "        if vat == [0] * l:return 0\n",
    "        res = 1000000\n",
    "        x = 1\n",
    "        for x in range(1,max(vat)+1):\n",
    "            m = x\n",
    "            for i in range(l):\n",
    "                vat[i] -= bucket[i]\n",
    "                if vat[i] > 0:\n",
    "                    m += vat[i]//x + (0 if vat[i]%x==0 else 1)\n",
    "            if m < res:res = m\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        maxK = max(vat)\n",
    "        if maxK == 0:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        for k in range(1,maxK + 1):\n",
    "            t = 0\n",
    "            for i in range(n):\n",
    "                t += max(0, math.ceil(vat[i] / k) - bucket[i])\n",
    "            res = min(res, t + k)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        maxk = max(vat)\n",
    "        if maxk == 0:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        for k in range(1, maxk + 1):\n",
    "            t = 0\n",
    "            for i in range(n):\n",
    "                t += max(0, (vat[i] + k - 1) // k - bucket[i])\n",
    "            res = min(res, t + k)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        l = len(bucket)\n",
    "        if vat == [0] * l:return 0\n",
    "        res = 1000000\n",
    "        x = 1\n",
    "        for x in range(1,max(vat)+l+2):\n",
    "            m = x\n",
    "            for i in range(l):\n",
    "                vat[i] -= bucket[i]\n",
    "                if vat[i] > 0:\n",
    "                    m += vat[i]//x + (0 if vat[i]%x==0 else 1)\n",
    "            if m < res:res = m\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        maxk = max(vat)\n",
    "        if maxk == 0:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        for k in range(1, maxk + 1):\n",
    "            t = 0\n",
    "            for i in range(n):\n",
    "                t += max(0, (vat[i] + k - 1) // k - bucket[i])\n",
    "            res = min(res, t + k)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        # 构建最大堆，放入每个vat需要填满的最少操作进行堆排序\n",
    "        h = []\n",
    "        count = 0\n",
    "        max_op = 1e9\n",
    "        for i in range(len(bucket)):\n",
    "            if not bucket[i] and vat:\n",
    "                count += 1\n",
    "                bucket[i] += 1\n",
    "            if vat[i]:\n",
    "                # (v+b-1)//b可以对(v/b)向上取整\n",
    "                heapq.heappush(h, [-((vat[i]+bucket[i]-1)//bucket[i]), i])\n",
    "        # 如果所有vat[i]都是0，则没有heappush\n",
    "        if not h: return 0\n",
    "        while count < max_op:\n",
    "            # y就是当前每个bucket需要蓄水的次数\n",
    "            y, i = heapq.heappop(h)\n",
    "            y = -y\n",
    "            max_op = min(max_op, count + y)\n",
    "            if y == 1:\n",
    "                break\n",
    "            # 求出需要让当前蓄水次数y减去1的bucket size[i]\n",
    "            new_bucket_i = (vat[i]+y-2)//(y-1)\n",
    "            count += new_bucket_i - bucket[i]\n",
    "            bucket[i] = new_bucket_i\n",
    "            heapq.heappush(h, [-((vat[i]+bucket[i]-1)//bucket[i]), i])\n",
    "        return max_op"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        maxk = max(vat)\n",
    "        if maxk == 0:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        for k in range(1, maxk + 1):\n",
    "            t = 0\n",
    "            for i in range(n):\n",
    "                t += max(0, (vat[i] + k -1) // k - bucket[i])\n",
    "            res = min(res, t + k)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        pq = []\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if bucket[i] == 0 and vat[i]:\n",
    "                cnt += 1\n",
    "                bucket[i] += 1\n",
    "            if vat[i] > 0:\n",
    "                pq.append([-ceil(vat[i]/bucket[i]), i])\n",
    "        heapq.heapify(pq)\n",
    "        if not pq:\n",
    "            ans = 0\n",
    "        else:\n",
    "            ans = inf\n",
    "            while cnt < ans:\n",
    "                v, i = heapq.heappop(pq)\n",
    "                v = -v\n",
    "                ans = min(ans, cnt + v)\n",
    "                if v == 1:\n",
    "                    break\n",
    "                t = ceil(vat[i] / (v - 1))\n",
    "                cnt += t - bucket[i]\n",
    "                bucket[i] = t\n",
    "                heapq.heappush(pq, [-ceil(vat[i]/bucket[i]), i])\n",
    "        # print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        # bucket = [1,3], vat = [6,8]\n",
    "        # 第 0 个水缸配的水桶容量为1，水缸的最低蓄水为6\n",
    "        # 第 1 个水缸配的水桶容量为3，水缸的最低蓄水位8\n",
    "\n",
    "        # 求最少的操作次数 \n",
    "\n",
    "        if max(vat) == 0:         \n",
    "            return 0\n",
    "        n = len(bucket)  \n",
    "\n",
    "        res = float('inf')  \n",
    "\n",
    "        min_pour_op = 1                #  已经知道不可能是0次了\n",
    "        max_pour_op = max(vat)          #  最多的情况（直接一次又一次地倒）这只是倾倒次数，升容次数再算。\n",
    "\n",
    "        for pour_time in range(min_pour_op, max_pour_op + 1):             # \n",
    "            cur = pour_time            #   总操作 = 倾倒 + 桶升容\n",
    "            for i in range(n):\n",
    "                ###### 桶的大小至少是多大\n",
    "                need_bucket_size = ceil(vat[i] / pour_time)\n",
    "                ###### 桶升容的次数\n",
    "                need_bucket_op = max(0, need_bucket_size - bucket[i])\n",
    "                ###### cur += 桶升容次数\n",
    "                cur += need_bucket_op\n",
    "            \n",
    "            res = min(res, cur)\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        mx = max(vat)\n",
    "        if mx == 0:\n",
    "            return 0\n",
    "        ans = inf\n",
    "        for x in range(1, mx + 1):\n",
    "            y = sum(max(0, (v + x - 1) // x - b) for v, b in zip(vat, bucket))\n",
    "            ans = min(ans, x + y)\n",
    "        return ans\n",
    "\n",
    "# 作者：ylb\n",
    "# 链接：https://leetcode.cn/problems/o8SXZn/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        mx = max(vat)\n",
    "        if mx == 0:\n",
    "            return 0\n",
    "        ans = inf\n",
    "        for x in range(1, mx + 1):\n",
    "            y = sum(max(0, (v + x - 1) // x - b) for v, b in zip(vat, bucket))\n",
    "            ans = min(ans, x + y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        maxvat = max(vat)\n",
    "        if maxvat == 0:\n",
    "            return 0\n",
    "        ans = float('inf')\n",
    "        for k in range(1,maxvat+1):\n",
    "            up = 0\n",
    "            for i in range(n):\n",
    "                up += max(0,(vat[i] + k - 1)//k - bucket[i])#(vat[i] + k - 1)//k - bucket[i]) = math.ceil(vat[i]/k) - bucket[i]\n",
    "            ans = min(ans,up + k)\n",
    "        return ans\n",
    "#         看代码的时候向上取整的计算困惑了我一会。尝试证明了一下。 (a+b-1) // b 等价于 ceil(a/b) 。证明如下：\n",
    "# 记a = mb+r 其中m为整除结果，r为余数\n",
    "# (a+b-1) // b = (mb+r+b-1) // b = m + 1 + (r-1)//b\n",
    "# 可以看到：\n",
    "# 当a / b不能整除时（r>=1）， (r-1)//b =0 此时式子结果为m+1\n",
    "# 当a / b能整除时（r = 0）， (r-1)//b =-1 此时式子结果为m\n",
    "# 故此实现了向上取整的效果。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def up(self, x, y):\n",
    "        return int((x - 1) / y) + 1\n",
    "\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        max_vat = max(vat)\n",
    "        if max_vat == 0:\n",
    "            return 0\n",
    "\n",
    "        ans = float('inf')\n",
    "        for storage in range(1, max_vat + 1):\n",
    "            tmp = storage\n",
    "            for j in range(len(bucket)):\n",
    "                rise = max(self.up(vat[j], storage) - bucket[j], 0)\n",
    "                tmp += rise\n",
    "            ans = min(ans, tmp)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        max_n = max(vat)\n",
    "        if max_n == 0:\n",
    "            return 0\n",
    "        cnt = 0\n",
    "        length = len(bucket)\n",
    "        for i in range(length):\n",
    "            if bucket[i] == 0:\n",
    "                bucket[i] += 1\n",
    "                cnt += 1\n",
    "        ret = float('inf')\n",
    "        for x in range(1, max_n+1):\n",
    "            cur = x\n",
    "            for i in range(length):\n",
    "                cur += max(0, vat[i] // x + int(vat[i] % x != 0) - bucket[i])\n",
    "            ret = min(cur, ret)\n",
    "        return ret+cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        ans = inf\n",
    "        mm = max(vat)\n",
    "        if mm == 0:\n",
    "            ans = 0\n",
    "        else:\n",
    "            for k in range(1, mm+1):\n",
    "                t = 0\n",
    "                for i in range(n):\n",
    "                    t += max(0, ceil(vat[i]/k) - bucket[i])   \n",
    "                ans = min(ans, t+k)\n",
    "        # print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        #copy\n",
    "        mx = max(vat)\n",
    "        if mx ==0:\n",
    "            return 0\n",
    "        ans = inf\n",
    "        for x in range(1,mx+1):\n",
    "            y = sum(max(0,(v+x-1)//x-b) for v,b in zip(vat,bucket))\n",
    "            ans = min(ans,x+y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        mx = max(vat)\n",
    "        if mx == 0:\n",
    "            return 0\n",
    "        ans = inf\n",
    "        for x in range(1, mx + 1): # 枚举蓄水次数 x，计算升级次数 y，x + y 的最小值就是答案\n",
    "            # 设蓄水前桶的容量为 p，那么 p * x >= vat[i]\n",
    "            # 又因为 p <= bucket[i] + y\n",
    "            # 联立得：y >= p - buckets[i] >= vat[i] / x - buckets[i]\n",
    "            # 其中 v + x - 1) // x 为每次需要最少得蓄水量\n",
    "            # v + x - 1) // x - b 就是需要升级的次数\n",
    "            # 全部加和就是答案\n",
    "            y = sum(max(0, (v + x - 1) // x - b) for v, b in zip(vat, bucket))\n",
    "            ans = min(ans, x + y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        maxk = max(vat)\n",
    "        if maxk == 0:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        for k in range(1, maxk + 1):\n",
    "            t = 0\n",
    "            for i in range(n):\n",
    "                t += max(0, (vat[i] + k - 1) // k - bucket[i])\n",
    "            res = min(res, t + k)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        heap, cnt, res, opt = [], 0, max(vat), 0\n",
    "        if res==0: return 0\n",
    "        for i,j in zip(bucket,vat):\n",
    "            if j==0: continue\n",
    "            if i==0: i, cnt = 1, cnt + 1\n",
    "            heapq.heappush(heap, [-math.ceil(j/i),i,j])\n",
    "        \n",
    "        while opt < res:\n",
    "            res = min(res, opt-heap[0][0])\n",
    "            k,i,j = heap[0]\n",
    "            if k>=-2: break\n",
    "            new = [-math.ceil(j/(i+1)),i+1,j]\n",
    "            heapq.heapreplace(heap, new)\n",
    "            opt += 1\n",
    "        return res + cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        mx = max(vat)\n",
    "        if mx == 0:\n",
    "            return 0\n",
    "        ans = float('inf')\n",
    "        for x in range(1, mx + 1):\n",
    "            y = sum(max(0, (v + x - 1) // x - b) for v, b in zip(vat, bucket))\n",
    "            ans = min(ans, x + y)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        ans = inf\n",
    "        mm = max(vat)\n",
    "        if mm == 0:\n",
    "            ans = 0\n",
    "        else:\n",
    "            for k in range(1, mm+1):\n",
    "                t = 0\n",
    "                for i in range(n):\n",
    "                    t += max(0, ceil(vat[i]/k) - bucket[i])\n",
    "                ans = min(ans, t+k)\n",
    "        # print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        pq = []\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if bucket[i] == 0 and vat[i]:\n",
    "                cnt += 1\n",
    "                bucket[i] += 1\n",
    "            if vat[i] > 0:\n",
    "                heapq.heappush(pq, [-((vat[i] + bucket[i] - 1) // bucket[i]), i])\n",
    "        if not pq:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        while cnt < res:\n",
    "            v, i = heapq.heappop(pq)\n",
    "            v = -v\n",
    "            res = min(res, cnt + v)\n",
    "            if v == 1:\n",
    "                break\n",
    "            t = (vat[i] + v - 2) // (v - 1)\n",
    "            cnt += t - bucket[i]\n",
    "            bucket[i] = t\n",
    "            heapq.heappush(pq, [-((vat[i] + bucket[i] - 1) // bucket[i]), i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        mx = max(vat)\n",
    "        if mx == 0:\n",
    "            return 0\n",
    "        ans = inf\n",
    "        for x in range(1, mx + 1):\n",
    "            y = sum(max(0, (v + x - 1) // x - b) for v, b in zip(vat, bucket))\n",
    "            ans = min(ans, x + y)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        maxk = max(vat)\n",
    "        if maxk == 0:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        for k in range(1, maxk + 1):\n",
    "            t = 0\n",
    "            for i in range(n):\n",
    "                t += max(0, (vat[i] + k-1 ) // k - bucket[i])\n",
    "            res = min(res, t + k)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 给定 N 个无限容量且初始均空的水缸，每个水缸配有一个水桶用来打水，第 i 个水缸配备的水桶容量记作 bucket[i]。小扣有以下两种操作：\n",
    "\n",
    "# 升级水桶：选择任意一个水桶，使其容量增加为 bucket[i]+1\n",
    "# 蓄水：将全部水桶接满水，倒入各自对应的水缸\n",
    "# 每个水缸对应最低蓄水量记作 vat[i]，返回小扣至少需要多少次操作可以完成所有水缸蓄水要求。\n",
    "\n",
    "# 注意：实际蓄水量 达到或超过 最低蓄水量，即完成蓄水要求。\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        maxk = max(vat)\n",
    "        if maxk == 0:\n",
    "            return 0\n",
    "\n",
    "        res = float('inf')\n",
    "        for k in range(1, maxk + 1):\n",
    "            t = 0\n",
    "            for i in range(n):\n",
    "                t += max(0, (vat[i] + k - 1) // k - bucket[i])\n",
    "            res = min(res, t + k)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        maxk = max(vat)\n",
    "        if maxk == 0:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        for k in range(1, maxk + 1):\n",
    "            t = 0\n",
    "            for i in range(n):\n",
    "                t += max(0, (vat[i] + k - 1) // k - bucket[i])\n",
    "            res = min(res, t + k)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        mx = max(vat)\n",
    "        if mx == 0:\n",
    "            return 0\n",
    "        ans = inf\n",
    "        for x in range(1,mx+1):\n",
    "            y = sum(max(0, (v + x - 1) // x - b)for v, b in zip(vat, bucket))\n",
    "            ans = min(ans, x + y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        # 枚举，选择最小值\n",
    "        mx = max(vat)\n",
    "        if mx == 0:\n",
    "            return 0\n",
    "        \n",
    "        ans = float('inf')\n",
    "        # x 是倒水次数，最大值就是不升级，用1强行倒满，最小是1次\n",
    "        for x in range(1, mx+1):\n",
    "            y = 0\n",
    "            for v, b in zip(vat, bucket):\n",
    "                # y 是升级次数，x 已确定的时候，计算y = v / x - b\n",
    "                # 向上取整，y = v // x + 1 -任何一个东西 - b\n",
    "                # 不能直接 v // x + 1\n",
    "                # 每一组都要统计一下\n",
    "                y += max(0, (v+x-1) // x - b)\n",
    "            ans = min(ans, x+y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        maxk = max(vat)\n",
    "        if maxk == 0:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        for k in range(1, maxk + 1):\n",
    "            t = 0\n",
    "            for i in range(n):\n",
    "                t += max(0, (vat[i] + k - 1) // k - bucket[i])\n",
    "            res = min(res, t + k)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        maxk = max(vat)\n",
    "        if maxk == 0:\n",
    "            return 0\n",
    "        \n",
    "        res = float('inf')\n",
    "        for k in range(1, maxk + 1):\n",
    "            t = 0\n",
    "            for i in range(n):\n",
    "                t += max(0, (vat[i] + k - 1) // k - bucket[i])\n",
    "            res = min(res, t + k)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        max_vat = max(vat)\n",
    "        if max_vat == 0:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        for k in range(1,max_vat + 1):\n",
    "            t = 0 \n",
    "            for i in range(len(bucket)):\n",
    "                t += max((vat[i] + k - 1) // k - bucket[i], 0 )\n",
    "            res =  min(res,t + k)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        mx = max(vat)\n",
    "        if mx == 0:\n",
    "            return 0\n",
    "        ans = inf\n",
    "        for x in range(1, mx + 1):\n",
    "            y = sum(max(0, (v + x - 1) // x - b) for v, b in zip(vat, bucket))\n",
    "            ans = min(ans, x + y)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        mx= max(vat)\n",
    "        if mx== 0:\n",
    "            return 0\n",
    "        ans= inf\n",
    "        for x in range(1, mx+ 1):\n",
    "            y= sum(max(0, (v+x -1)//x - b) for v, b in zip(vat,bucket))\n",
    "            ans= min(ans, x+y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        maxk = max(vat)\n",
    "        if maxk == 0:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        for k in range(1, maxk + 1):\n",
    "            t = 0\n",
    "            for i in range(n):\n",
    "                t += max(0, (vat[i] + k - 1) // k - bucket[i])\n",
    "            res = min(res, t + k)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        maxk = max(vat)\n",
    "        if maxk == 0:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        for k in range(1, maxk + 1):\n",
    "            t = 0\n",
    "            for i in range(n):\n",
    "                t += max(0, (vat[i] + k - 1) // k - bucket[i])\n",
    "            res = min(res, t + k)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        ans = inf\n",
    "        for x in range(1, max(vat) + 1):\n",
    "            y = sum(max(0, ceil(v / x) - b) for b, v in zip(bucket, vat))\n",
    "            ans = min(ans, x + y)\n",
    "        return 0 if ans == inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        if max(vat) == 0:\n",
    "            return 0\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if bucket[i] == 0:\n",
    "                cnt += 1\n",
    "                bucket[i] = 1\n",
    "        store = max([ceil(vat[i]/bucket[i]) for i in range(n)])\n",
    "        ans = store + cnt\n",
    "        for x in range(store - 1,0,-1): \n",
    "            upgrade = sum(max(ceil(vat[i]/x) - bucket[i],0) for i in range(n))\n",
    "            ans = min(ans, x + upgrade + cnt)\n",
    "\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        ans = 0 if max(vat) ==0 else max(vat) + bucket.count(0) \n",
    "        for k in range(1,max(vat)+1):\n",
    "            if k > ans:\n",
    "                break\n",
    "            lst = [0] *len(bucket)\n",
    "            for i in range(len(bucket)):\n",
    "                lst[i] = max(math.ceil(vat[i]/k) - bucket[i],0)\n",
    "            tmp = sum(lst)+k\n",
    "            ans = min(ans,tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        maxK = max(vat)\n",
    "        if maxK == 0:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        for k in range(1,maxK + 1):\n",
    "            t = 0\n",
    "            for i in range(n):\n",
    "                t += max(0, (vat[i] - 1) // k + 1 - bucket[i])\n",
    "            res = min(res, t + k)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        maxK = max(vat)\n",
    "        if maxK == 0:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        for k in range(1,maxK + 1):\n",
    "            t = 0\n",
    "            for i in range(n):\n",
    "                t += max(0, (vat[i] + k - 1) // k - bucket[i])\n",
    "            res = min(res, t + k)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        mx = max(vat)\n",
    "        if mx == 0:\n",
    "            return 0\n",
    "        ans = inf\n",
    "        for x in range(1, mx + 1):\n",
    "            y = sum(max(0, (v + x - 1) // x - b) for v, b in zip(vat, bucket))\n",
    "            ans = min(ans, x + y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        pq = []\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if bucket[i] == 0 and vat[i]:\n",
    "                cnt += 1\n",
    "                bucket[i] += 1\n",
    "            if vat[i] > 0:\n",
    "                heapq.heappush(pq, [-((vat[i] + bucket[i] - 1) // bucket[i]), i])\n",
    "        if not pq:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        while cnt < res:\n",
    "            v, i = heapq.heappop(pq)\n",
    "            v = -v\n",
    "            res = min(res, cnt + v)\n",
    "            if v == 1:\n",
    "                break\n",
    "            t = (vat[i] + v - 2) // (v - 1)\n",
    "            cnt += t - bucket[i]\n",
    "            bucket[i] = t\n",
    "            heapq.heappush(pq, [-((vat[i] + bucket[i] - 1) // bucket[i]), i])\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        maxk = max(vat)\n",
    "        if maxk == 0:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        for k in range(1, maxk + 1):\n",
    "            t = 0\n",
    "            for i in range(n):\n",
    "                t += max(0, (vat[i] + k - 1) // k - bucket[i])\n",
    "            res = min(res, t + k)\n",
    "        return res\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        \n",
    "        add = 0\n",
    "        maxHeap = []\n",
    "        for i in range(n):\n",
    "            b, v = bucket[i], vat[i]\n",
    "            if b == 0 and v != 0:\n",
    "                bucket[i] += 1\n",
    "                add += 1\n",
    "            if v > 0:\n",
    "                op = (vat[i] + bucket[i] - 1) // bucket[i]\n",
    "                heapq.heappush(maxHeap, (-op, i))\n",
    "        \n",
    "        if len(maxHeap) == 0:\n",
    "            return 0\n",
    "        res = 10 ** 9\n",
    "        while add < res:\n",
    "            op, i = heapq.heappop(maxHeap)\n",
    "            op *= (-1)\n",
    "            res = min(res, op + add)\n",
    "            if op == 1:\n",
    "                break\n",
    "\n",
    "            new_op = op - 1\n",
    "            new_bucket = (vat[i] + new_op - 1) // new_op\n",
    "            new_add = new_bucket - bucket[i]\n",
    "            add += new_add\n",
    "            bucket[i] = new_bucket\n",
    "\n",
    "            heapq.heappush(maxHeap, (-new_op, i))\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        mx = max(vat)\n",
    "        if mx == 0:\n",
    "            return 0\n",
    "        ans = inf\n",
    "        for x in range(1, mx + 1):\n",
    "            y = sum(max(0, (v + x - 1) // x - b) for v, b in zip(vat, bucket))\n",
    "            ans = min(ans, x + y)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        mx = max(vat)\n",
    "        if mx == 0:\n",
    "            return 0\n",
    "        ans = inf\n",
    "        for x in range(1, mx + 1):\n",
    "            y = sum(max(0, (v + x - 1) // x - b) for v, b in zip(vat, bucket))\n",
    "            ans = min(ans, x + y)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        pq = []\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if bucket[i] == 0 and vat[i]:\n",
    "                cnt += 1\n",
    "                bucket[i] += 1\n",
    "            if vat[i] > 0:\n",
    "                pq.append([-((vat[i] + bucket[i] - 1) // bucket[i]), i])\n",
    "        heapq.heapify(pq)\n",
    "        if not pq:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        while cnt < res:\n",
    "            v, i = heapq.heappop(pq)\n",
    "            v = -v\n",
    "            res = min(res, cnt + v)\n",
    "            if v == 1:\n",
    "                break\n",
    "            t = (vat[i] + v - 2) // (v - 1)\n",
    "            cnt += t - bucket[i]\n",
    "            bucket[i] = t\n",
    "            heapq.heappush(pq, [-((vat[i] + bucket[i] - 1) // bucket[i]), i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        maxk = max(vat)\n",
    "        if maxk == 0:\n",
    "            return 0\n",
    "        \n",
    "        res=float('inf')\n",
    "        for k in range(1, maxk+1):\n",
    "            t = 0\n",
    "            for i in range(n):\n",
    "                t += max(0, math.ceil(vat[i]/k) - bucket[i])\n",
    "            res = min(res, t+k)\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        mx = max(vat)\n",
    "        if mx == 0:\n",
    "            return 0\n",
    "        ans = inf\n",
    "        for x in range(1, mx + 1):\n",
    "            y = sum(max(0, (v + x - 1) // x - b) for v, b in zip(vat, bucket))\n",
    "            ans = min(ans, x + y)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        mx = max(vat)\n",
    "        if not mx: return 0\n",
    "        ans = inf\n",
    "        for k in range(1,mx+1):\n",
    "            step = sum(max(0,math.ceil(v/k)-b) for v, b in zip(vat,bucket))\n",
    "            ans = min(ans,step+k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        if max(vat) == 0:\n",
    "            return 0\n",
    "        n = len(bucket)\n",
    "        res = float('inf')\n",
    "\n",
    "        min_pour_op = 1\n",
    "        max_pour_op = max(vat)\n",
    "\n",
    "        for pour_time in range(min_pour_op, max_pour_op + 1):\n",
    "            cur = pour_time\n",
    "            for i in range(n):\n",
    "                need_bucket_size = ceil(vat[i] / pour_time)\n",
    "                need_bucket_op = max(0, need_bucket_size - bucket[i])\n",
    "                cur += need_bucket_op\n",
    "            res = min(res, cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        h = []\n",
    "        num_ops = 0\n",
    "        for i in range(n):\n",
    "            if bucket[i] == 0 and vat[i] > 0:\n",
    "                num_ops += 1\n",
    "                bucket[i] += 1\n",
    "            if vat[i] > 0:\n",
    "                heapq.heappush(h, (-self.get_num_ops(vat[i], bucket[i]), i))\n",
    "        if len(h) == 0:\n",
    "            return 0\n",
    "        min_ops = 10000000\n",
    "        while num_ops < min_ops:\n",
    "            ops, i = heapq.heappop(h)\n",
    "            ops *= -1\n",
    "            min_ops = min(min_ops, num_ops + ops)\n",
    "            if ops == 1:\n",
    "                break\n",
    "            new_bucket = self.get_num_ops(vat[i], ops - 1)\n",
    "            num_ops += new_bucket - bucket[i]\n",
    "            bucket[i] = new_bucket\n",
    "            heapq.heappush(h, (-self.get_num_ops(vat[i], bucket[i]), i))\n",
    "        return min_ops\n",
    "\n",
    "    def get_num_ops(self, amount: int, unit: int) -> int:\n",
    "        num_ops = amount // unit\n",
    "        if amount % unit != 0:\n",
    "            num_ops += 1\n",
    "        return num_ops"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        heap = []\n",
    "        n = len(bucket)\n",
    "        cnt = 0\n",
    "\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if bucket[i] == 0:\n",
    "                if vat[i] == 0:\n",
    "                    i += 1\n",
    "                    continue\n",
    "                else:\n",
    "                    bucket[i] += 1\n",
    "                    cnt += 1\n",
    "            heappush(heap, (-ceil(vat[i] / bucket[i]), bucket[i], vat[i]))\n",
    "            i += 1\n",
    "        min_value = inf\n",
    "        while len(heap) > 0:\n",
    "            item = heappop(heap)\n",
    "            tmp = ceil(item[2] / (item[1] + 1))\n",
    "            min_value = min(min_value, cnt - item[0])\n",
    "            if -item[0] >= tmp + 1:\n",
    "                cnt += 1\n",
    "                heappush(heap, (-tmp, item[1] + 1, item[2]))\n",
    "                min_value = min(min_value, cnt - nsmallest(1, heap)[0][0])\n",
    "            else:\n",
    "                heappush(heap, item)\n",
    "                break\n",
    "        return min_value if min_value != inf else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heapify, heapreplace\n",
    "from math import ceil\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        que = [(-ceil(b/a) if a>0 else -b-1, a, b) for a, b in zip(bucket, vat) if b>0]\n",
    "        if not len(que):\n",
    "            return 0\n",
    "        heapify(que)\n",
    "        # print(que)\n",
    "        upgrade_cnt, ret = 0, 100000\n",
    "        while True:\n",
    "            c, b, v = que[0]\n",
    "            if upgrade_cnt >= ret:\n",
    "                break\n",
    "            ret = min(ret, upgrade_cnt-c)\n",
    "            if c==-1:\n",
    "                break\n",
    "            new_b = ceil(v/(-c-1))\n",
    "            upgrade_cnt += new_b-b\n",
    "            heapreplace(que, (c+1, new_b, v))\n",
    "            # print(que)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        pq = []\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if bucket[i] == 0 and vat[i]:\n",
    "                cnt += 1\n",
    "                bucket[i] += 1\n",
    "            if vat[i] > 0:\n",
    "                heapq.heappush(pq, [-((vat[i] + bucket[i] - 1) // bucket[i]), i])\n",
    "        if not pq:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        while cnt < res:\n",
    "            v, i = heapq.heappop(pq)\n",
    "            v = -v\n",
    "            res = min(res, cnt + v)\n",
    "            if v == 1:\n",
    "                break\n",
    "            t = (vat[i] + v - 2) // (v - 1)\n",
    "            cnt += t - bucket[i]\n",
    "            bucket[i] = t\n",
    "            heapq.heappush(pq, [-((vat[i] + bucket[i] - 1) // bucket[i]), i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        maxk = max(vat)\n",
    "        if maxk==0:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        for k in range(1,maxk+1):\n",
    "            t = 0\n",
    "            for i in range(n):\n",
    "                t += max(0,math.ceil(vat[i]/k)-bucket[i])\n",
    "            res = min(res,t+k)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        heap = []\n",
    "        n = len(bucket)\n",
    "        cnt = 0\n",
    "\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if bucket[i] == 0:\n",
    "                if vat[i] == 0:\n",
    "                    i += 1\n",
    "                    continue\n",
    "                else:\n",
    "                    bucket[i] += 1\n",
    "                    cnt += 1\n",
    "            heappush(heap, (-ceil(vat[i] / bucket[i]), bucket[i], vat[i]))\n",
    "            i += 1\n",
    "        min_value = inf\n",
    "        while len(heap) > 0:\n",
    "            item = heappop(heap)\n",
    "            tmp = ceil(item[2] / (item[1] + 1))\n",
    "            min_value = min(min_value, cnt - item[0])\n",
    "            if -item[0] >= tmp + 1:\n",
    "                cnt += 1\n",
    "                heappush(heap, (-tmp, item[1] + 1, item[2]))\n",
    "                min_value = min(min_value, cnt - nsmallest(1, heap)[0][0])\n",
    "            else:\n",
    "                heappush(heap, item)\n",
    "                break\n",
    "        return min_value if min_value != inf else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        mx = max(vat)\n",
    "        if mx == 0:\n",
    "            return 0\n",
    "        ans = inf\n",
    "        for x in range(1, mx + 1):\n",
    "            y = sum(max(0, (v + x - 1) // x - b) for v, b in zip(vat, bucket))\n",
    "            ans = min(ans, x + y)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        pq = []\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if bucket[i] == 0 and vat[i]:\n",
    "                cnt += 1\n",
    "                bucket[i] += 1\n",
    "            if vat[i] > 0:\n",
    "                heapq.heappush(pq, [-((vat[i] + bucket[i] - 1) // bucket[i]), i])\n",
    "        if not pq:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        while cnt < res:\n",
    "            v, i = heapq.heappop(pq)\n",
    "            v = -v\n",
    "            res = min(res, cnt + v)\n",
    "            if v == 1:\n",
    "                break\n",
    "            t = (vat[i] + v - 2) // (v - 1)\n",
    "            cnt += t - bucket[i]\n",
    "            bucket[i] = t\n",
    "            heapq.heappush(pq, [-((vat[i] + bucket[i] - 1) // bucket[i]), i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n=len(bucket)\n",
    "        maxk=max(vat)\n",
    "        if maxk==0:\n",
    "            return 0\n",
    "        res=float('inf')\n",
    "        for k in range(1,maxk+1):\n",
    "            t=0\n",
    "            for i in range(n):\n",
    "                t+=max(0,(vat[i]+k-1)//k-bucket[i])\n",
    "            res=min(res,t+k)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        pq = []\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if bucket[i] == 0 and vat[i]:\n",
    "                cnt += 1\n",
    "                bucket[i] += 1\n",
    "            if vat[i] > 0:\n",
    "                heapq.heappush(pq, [-((vat[i] + bucket[i] - 1) // bucket[i]), i])\n",
    "        if not pq:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        while cnt < res:\n",
    "            v, i = heapq.heappop(pq)\n",
    "            v = -v\n",
    "            res = min(res, cnt + v)\n",
    "            if v == 1:\n",
    "                break\n",
    "            t = (vat[i] + v - 2) // (v - 1)\n",
    "            cnt += t - bucket[i]\n",
    "            bucket[i] = t\n",
    "            heapq.heappush(pq, [-((vat[i] + bucket[i] - 1) // bucket[i]), i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        right = max(vat)\n",
    "        if right == 0:\n",
    "            return 0\n",
    "        \n",
    "        cnt = 0\n",
    "        f = [0] * (right + 1)\n",
    "        f[0] = inf\n",
    "        for b, v in zip(bucket, vat):\n",
    "            if v == 0:\n",
    "                continue\n",
    "            if b == 0:\n",
    "                b += 1\n",
    "                cnt += 1\n",
    "            \n",
    "            for i in range(1, right+1):\n",
    "                upgrade = (v + i - 1) // i - b\n",
    "                if upgrade > 0:\n",
    "                    f[i] += upgrade\n",
    "                else:\n",
    "                    break\n",
    "        \n",
    "        return min(i + x for i, x in enumerate(f)) + cnt\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        maxk = max(vat)\n",
    "        if maxk == 0:\n",
    "            return 0\n",
    "\n",
    "        res = float('inf')\n",
    "        # k表示打水次数\n",
    "        for k in range(1, maxk + 1):\n",
    "            # t 表示每个水桶的升级次数\n",
    "            t = 0\n",
    "            for i in range(n):\n",
    "                # vat[i] + k - 1) // k  打水k下，水桶最少容量，并向上取整\n",
    "                t += max(0, (vat[i] + k - 1) // k - bucket[i])\n",
    "            res = min(res, t + k)\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        print(ceil(9999 / 2))\n",
    "        heap = []\n",
    "        n = len(bucket)\n",
    "        cnt = 0\n",
    "\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if bucket[i] == 0:\n",
    "                if vat[i] == 0:\n",
    "                    i += 1\n",
    "                    continue\n",
    "                else:\n",
    "                    bucket[i] += 1\n",
    "                    cnt += 1\n",
    "            heappush(heap, (-ceil(vat[i] / bucket[i]), bucket[i], vat[i]))\n",
    "            i += 1\n",
    "        min_value = inf\n",
    "        while len(heap) > 0:\n",
    "            item = heappop(heap)\n",
    "            tmp = ceil(item[2] / (item[1] + 1))\n",
    "            min_value = min(min_value, cnt - item[0])\n",
    "            print(f\"item:{item} cnt:{cnt} sum:{cnt - item[0]}\")\n",
    "            if -item[0] >= tmp + 1:\n",
    "                cnt += 1\n",
    "                heappush(heap, (-tmp, item[1] + 1, item[2]))\n",
    "                min_value = min(min_value, cnt - nsmallest(1, heap)[0][0])\n",
    "            else:\n",
    "                heappush(heap, item)\n",
    "                break\n",
    "        return min_value if min_value != inf else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        mx = max(vat)\n",
    "        if mx == 0:\n",
    "            return 0\n",
    "        ans = inf\n",
    "        for x in range(1, mx + 1):\n",
    "            y = sum(max(0, (v + x - 1) // x - b) for v, b in zip(vat, bucket))\n",
    "            ans = min(ans, x + y)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        if all(v == 0 for v in vat):\n",
    "            return 0\n",
    "        l, r = 1, max(ceil(v / b) if b > 0 else v + 1 for (b, v) in zip(bucket, vat))\n",
    "        return min(fill + sum(max(ceil(v / fill) - b, 0) for (b, v) in zip(bucket, vat)) for fill in range(l, r + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# 贪心 + 暴力枚举蓄水次数\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "\n",
    "        right = 0\n",
    "        for b, v in zip(bucket, vat):\n",
    "            if b == 0:\n",
    "                b += 1\n",
    "            right = max(right, (v + b - 1) // b)\n",
    "\n",
    "        # 特判\n",
    "        if right == 0:\n",
    "            return 0\n",
    "\n",
    "        ans = 1e18\n",
    "        for k in range(1, right + 1):\n",
    "            cnt = 0\n",
    "            for b, v in zip(bucket, vat):\n",
    "                if b == 0:\n",
    "                    b += 1\n",
    "                    cnt += 1\n",
    "                cnt += max((v + k - 1) // k - b, 0)\n",
    "            ans = min(ans, cnt + k)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        maxk = max(vat)\n",
    "        if maxk == 0:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        for k in range(1, maxk + 1):\n",
    "            t = 0\n",
    "            for i in range(n):\n",
    "                t += max(0, (vat[i] + k - 1) // k - bucket[i])\n",
    "            res = min(res, t + k)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        heap = []\n",
    "        n = len(bucket)\n",
    "        cnt = 0\n",
    "\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if bucket[i] == 0:\n",
    "                if vat[i] == 0:\n",
    "                    i += 1\n",
    "                    continue\n",
    "                else:\n",
    "                    bucket[i] += 1\n",
    "                    cnt += 1\n",
    "            heappush(heap, (-ceil(vat[i] / bucket[i]), bucket[i], vat[i]))\n",
    "            i += 1\n",
    "        min_value = inf\n",
    "        while len(heap) > 0:\n",
    "            item = heappop(heap)\n",
    "            tmp = ceil(item[2] / (item[1] + 1))\n",
    "            min_value = min(min_value, cnt - item[0])\n",
    "            if -item[0] >= tmp + 1:\n",
    "                cnt += 1\n",
    "                heappush(heap, (-tmp, item[1] + 1, item[2]))\n",
    "                min_value = min(min_value, cnt - nsmallest(1, heap)[0][0])\n",
    "            else:\n",
    "                heappush(heap, item)\n",
    "                break\n",
    "        return min_value if min_value != inf else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        # 使用大根堆来保存(倒水次数,水桶容量,蓄水量)三元组\n",
    "        n=len(bucket)\n",
    "        queue=[]\n",
    "        count=0\n",
    "        for i in range(n):\n",
    "            if bucket[i]==0 and vat[i]>0:\n",
    "                count+=1\n",
    "                bucket[i]+=1\n",
    "            if vat[i]>0:\n",
    "                heapq.heappush(queue, (-((vat[i]-1)//bucket[i]+1),i))\n",
    "        if queue==[]:\n",
    "            return 0\n",
    "        res=2147483647\n",
    "        while count<res:\n",
    "            volume,i=heapq.heappop(queue)\n",
    "            volume=-volume\n",
    "            res=min(res,count+volume)\n",
    "            if volume==1:\n",
    "                break\n",
    "            t=(vat[i]-1)//(volume-1)+1\n",
    "            count+=t-bucket[i]\n",
    "            bucket[i]=t\n",
    "            heapq.heappush(queue, (-((vat[i]-1)//bucket[i]+1),i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "        n = len(bucket)\n",
    "        if max(vat) == 0: return 0\n",
    "        ans = max(vat) + 1\n",
    "        for i in range(1, max(vat) + 1):\n",
    "            times = [max((vat[j] - 1) // i + 1 - bucket[j], 0) for j in range(n)]\n",
    "            ans = min(ans, sum(times) + i)\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def storeWater(self, bucket: List[int], vat: List[int]) -> int:\n",
    "\n",
    "        if not vat or max(vat) == 0:\n",
    "            return 0\n",
    "        \n",
    "        maxVat = max(vat)\n",
    "\n",
    "        res = inf\n",
    "\n",
    "        for i in range(1, maxVat + 1):\n",
    "            addBuckets = 0\n",
    "            for j in range(len(vat)):\n",
    "                # calculate update nums\n",
    "                currentBucket = vat[j] // i\n",
    "                if vat[j] % i != 0:\n",
    "                    currentBucket += 1\n",
    "                # if bucket[j] is big enough then no need to add\n",
    "                addBuckets += max(0, (currentBucket-bucket[j]))\n",
    "            res = min(res, addBuckets + i)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
